树的直径是一个非常经典的概念,具体定义就是一颗树上的最长链。
关于直径有一个非常常见的结论:可以通过两次来求得树上的一条直径(直径是可以不唯一的)。首先随便选择一个点往外遍历找到能到达的最远点,再从出发往外走走到最远点,则到的一条简单路径就是树的直径。
这个结论的证明分为两步:
贪心时的第二步最远点显然是正确的,一定能拿到最远距离的。
第一步是证明:从树上任意一点出发走到的最远点,一定是树上直径的一个端点。
反证法:假设某个点走出去的最远点是而拓展出去得到的一个直径的候选项短于另外一组同样方式求的的和,那么无非就两种情况,第一种是两者不相交,如下图:

由于整个图是联通的,我们可以找到一个点链接两个直径,如图:

根据定义:是比长的,否则不会选择,但是这样的话对于来说,选择与连通明显更优,与他是最长的直径矛盾了,这种情况下只有当假设正确的时候,也就是两者相等都是树上的直径的时候才是正确的。
第二个是假设他俩是相交于一点Z的话,如下
显然在交于某一点Z的时候,根据最远点的定义,一定有即是三者中最长的,但是这样的话,点应该选择连通向而不是,这就矛盾了,所以第二种情况也是不成立的,因为只有在假设正确的时候,也即是两者相等都是直径的时候,才不矛盾。
综上,结论是正确的,即从树上任意一点出发走到的最远点一定是直径的一个端点。
参考代码如下:
注意这个代码只是部分,是要跑两次的,就是最终的最远点。
void dfs(int u,int& t)
{
st[u] = 1;
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(st[v] == 1) continue;
dist[v] = dist[u] + cost[i];
if(dist[v] >= dist[t]) t = v;
dfs(v,t);
}
st[u] = 0;
}
但是这种贪心做法仅能应对所有权都是正权的情况,如果图里有负权,就不能用了。
在这种情况下就得用树形DP来做了,DP的具体内容就不详细展开了,说简单一点。
首先,直径如果包含节点,则一截是往他的子树下伸展得到,另一截是另一个子树伸展出去得到,形成的一条链。
定义:为节点往以为根的子树下走,能走到的所有长度集合中最大的。
转移:D[x] = max{D[S] + edge(x,S)
其中是的一个子节点,表示两点连边的权值。
其次,还得把另一边加上。
定义:F{x]是以为中间点形成的一条链的所有长度集合里最大的。
转移:
注意和是不能相同的,不然会重复计算,因此,具体代码时要先更新再更新具体的距离。
参考代码如下:
这里没有明确地写出,直接记录并修改的最大值做完之后就是直径。
void dp(int u,int& t)
{
st[u] = 1;
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(st[v] == 1) continue;
dp(v,t);
t = max(t,dist[u] + dist[v] + cost[i]);
dist[u] = max(dist[u],dist[v] + cost[i]);
}
st[u] = 0;
}